package 十大算法;

import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * Sorts.class
 *
 * @author tingwen
 * @date date
 */
public class Sorts {


    public static void main(String args[]) {
        Integer[] ints = {22, 33, 11, 1, 2};
        List<Integer> list = Arrays.asList(ints);

        long start = System.currentTimeMillis();
        mergeSort(ints);
        long end = System.currentTimeMillis();
        System.out.println("end = " + (end - start));
        System.out.println(Arrays.toString(ints));

        long start1 = System.currentTimeMillis();
        Collections.sort(list, Integer::compareTo);
        long end1 = System.currentTimeMillis();
        System.out.println("end = " + (end1 - start1));


    }

    /**
     * Simple insertion sort 插入排序
     *
     * <p>
     * 描述： 该方法是升序
     */
    public static <T extends Comparable<? super T>> void insertionSort(T[] t) {
        int j;
        for (int i = 1; i < t.length; i++) {
            T tmp = t[i];  // 记录t[i] 的值
            for (j = i; j > 0 && tmp.compareTo(t[j - 1]) < 0; j--)  // 后面的值比前一个值小，则前面值后移
                t[j] = t[j - 1];
            t[j] = tmp;  // 直到 j=0 将记录的t[i] 放置到空位t[j]上
        }
    }

    /**
     * ShellSort 希尔排序
     */
    public static <T extends Comparable<? super T>> void shellSort(T[] t) {
        int j;
        for (int point = t.length / 2; point > 0; point /= 2) { // 此时 point 为增量序列，
            // 按增量序列 做 插入排序， 当point=1时, 序列基本有序，做最后一次插入排序
            for (int i = point; i < t.length; i++) {
                T temp = t[i];
                for (j = i; j >= point && temp.compareTo(t[j - point]) < 0; j -= point)
                    t[j] = t[j - point];
                t[j] = temp;
            }
        }
    }

    /**
     * MergeSort 归并排序
     * <p>
     * 空间换时间
     * 时间复杂度： 最坏：O(NlogN)
     */
    public static <T extends Comparable<? super T>> void mergeSort(T[] a) {
        T[] tmpArray = (T[]) new Comparable[a.length];

        MergeSort.sort(a, tmpArray, 0, a.length - 1);
    }


    /**
     * FastSort 快速排序
     * 对于很小的数组（N <= 20）,快速排序不如插入排序
     * <p>
     * 时间复杂度： 最坏：O(N^2)  平均时间：O(NlogN)
     */
    public static <T extends Comparable<? super T>> void fastSort(T[] t) {
        FastSort.sort(t, 0, t.length - 1);
    }


    /**
     * HeapSort 堆排序
     * 完全二叉树-->演进为二叉堆，
     * 二叉堆性质： 任意节点小于其子节点
     * 1. 通过 过上虑操作 创建一个 创建二叉堆
     * 2. 通过 下虑操作 删除最小单元，在堆顶
     * 时间复杂度： 最坏：O(NlogN)
     */
    public static <T extends Comparable<? super T>> void heapSort(T[] t) {

    }

    private static <T extends Comparable<? super T>> void swap(T[] t, int index1, int index2) {
        T temp = t[index2];
        t[index2] = t[index1];
        t[index1] = temp;
    }

    private static class FastSort {
        private static <T extends Comparable<? super T>> void sort(T[] t, int left, int rightEnd) {
            int leftPos = left;
            int rightPos = rightEnd;
            T key = t[left];
            while (rightPos > leftPos) {
                //从后往前比较
                while (rightPos > leftPos && key.compareTo(t[rightPos]) <= 0)  //如果没有比关键值小的，比较下一个，直到有比关键值小的交换位置，然后又从前往后比较
                    rightPos--;
                if (key.compareTo(t[rightPos]) >= 0) swap(t, leftPos, rightPos);

                //从前往后比较
                while (rightPos > leftPos && key.compareTo(t[leftPos]) >= 0)//如果没有比关键值大的，比较下一个，直到有比关键值大的交换位置
                    leftPos++;
                if (key.compareTo(t[leftPos]) <= 0) swap(t, leftPos, rightPos);

                //此时第一次循环比较结束，关键值的位置已经确定了。左边的值都比关键值小，右边的值都比关键值大，但是两边的顺序还有可能是不一样的，进行下面的递归调用
            }
            //递归
            if (leftPos > left) sort(t, left, leftPos - 1);//左边序列。第一个索引位置到关键值索引-1
            if (rightPos < rightEnd) sort(t, rightPos + 1, rightEnd);//右边序列。从关键值索引+1到最后一个
        }
    }

    private static class MergeSort {
        private static <T extends Comparable<? super T>> void sort(T[] a, T[] tmpArray, int left, int right) {
            if (left < right) {
                int center = (left + right) / 2;
                sort(a, tmpArray, left, center);
                sort(a, tmpArray, center + 1, right);
                merge(a, tmpArray, left, center + 1, right);
            }
        }

        private static <T extends Comparable<? super T>> void merge(T[] a, T[] tmpArray, int leftPos, int rightPos, int rightEnd) {
            int leftEnd = rightPos - 1;
            int tmpPos = leftPos;
            int numElements = rightEnd - leftPos + 1;

            while (leftPos <= leftEnd && rightPos <= rightEnd) {
                if (a[leftPos].compareTo(a[rightPos]) <= 0) {
                    tmpArray[tmpPos++] = a[leftPos++];
                } else {
                    tmpArray[tmpPos++] = a[rightPos++];
                }
            }

            while (leftPos <= leftEnd) {
                tmpArray[tmpPos++] = a[leftPos++];
            }
            while (rightPos <= rightEnd) {
                tmpArray[tmpPos++] = a[rightPos++];
            }

            for (int i = 0; i < numElements; i++, rightEnd--) {
                a[rightEnd] = tmpArray[rightEnd];
            }
        }
    }
}
